import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description：
 * User：user
 * DATE:2021-11-15
 * Time:14:30
 */
public class TestDemo {

    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //1.统计单词出现的次数
        for(String s: words){
            if(map.get(s) == null){
                map.put(s,1);
            }else{
                Integer val = map.get(s);
                map.put(s,val+1);
            }
        }
        //2.此时已经统计好了每个单词出现的次数了,接下来需要建立一个小根堆大小为K的小根堆
        //3.遍历你的map往小根堆里放
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });

        for (Map.Entry<String,Integer> entry : map.entrySet()){
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //频率相同，看字母，字母顺序小的入队
                if(top.getValue().compareTo(entry.getValue()) == 0){
                    if(top.getKey().compareTo(entry.getKey()) == 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return  ret;

    }


    //找到十万个数据中的第一个重复元素
    public  static  int func(int[] array){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])){
                set.add(array[i]);
            }else{
                return array[i];
            }
        }
        return  -1;
    }

    //去除十万个数据中的重复元素
    public  static  HashSet<Integer> func2(int[] array){
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
                set.add(array[i]);
        }
        return set;
    }

    //统计重复数据出现的次数
    public  static  HashMap<Integer,Integer> func3(int[] array){
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int key = array[i];
            if(null == map.get(key)){
                map.put(key,1);
            }else{
                int val = map.get(key);
                map.put(key,val+1);
            }
        }
        return  map;
    }


    //查找十个元素中的第一个重复的元素
    public  static  void main(String[] args){
        int[] array = new int[1_000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(500);
        }
        /*int ret = func(array);
        if(ret == -1){
            System.out.println("没有重复的数据");
        }else{
            System.out.println("第一个重复的数据是："+ret);
        }*/

       /* Iterator<Integer> it = ret.iterator();
       while (it.hasNext()){
           System.out.print(it.next());
       }*/
       /* HashSet<Integer> ret = func2(array);
        System.out.println(ret);*/
        //其实现在还是无序的？为什么结果上来看他还是游学的呢？答案：这是一种巧合？
        //因为hashSetde的底层是一个hashMap -》存放元素的时候，是根据函数来定义存放的位置的
        //目前的数据正好是整数，通过这个哈希函数把数据放到hashset的时候，就出现了正好的，反到位置变的有序多了
        HashMap<Integer,Integer> map = func3(array);
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            System.out.println("数字：" + entry.getKey() + "次数" + entry.getValue());
        }
    }

    public static void main2(String[] args) {
        //set是一个存放不重复元素的集合
        Set<String> set  =  new HashSet<>();
        set.add("张三");
        set.add("李四");
        set.add("bit");
        set.add("null");//普通的可以放入null 但是TreeSet不可以放入


        //作业：搜集以下有关迭代器的面试问题
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            System.out.println(it.next());
        }
        System.out.println("====================");
        //set.add("bit");//元素不能重复 如果重复只能存在一个
        System.out.println(set);//无序的集合
        System.out.println(set.size());
    }
    public static void main1(String[] args) {
        Map<String,String> map = new HashMap<>();
        map.put("及时雨","宋江");
        map.put("悟净","沙僧");
        //map.put("悟净","沙僧2");//打印的结果是 沙僧2  key是可以重复的 但是你的value值会被更新为最后的value
        map.put("null","沙僧");//key可以是null
        map.put("null","null");//key可以是null value也可以是null


        //HashMap是一个无序的数据结构
        //无序不是大小顺序，是存放顺序
        //为什么会出现这样的情况？因为map存放元素的时候，踏实更具一定的个规则存放的
        //规则:通过key和哈希函数的作用


        //不能通过迭代器实现之直接遍历map 是因为没有实现Iterable
        Set<Map.Entry<String,String>> entrySet = map.entrySet();
        for (Map.Entry<String,String> entry:entrySet) {
            System.out.println("key"+entry.getKey() + " value" + entry.getValue());
            //setValue(value)
        }
        System.out.println("==================================");

        Set<String> set = map.keySet();//返回所有的key
        System.out.println(set);
        System.out.println("==================================");

        Collection<String> collection = map.values();
        System.out.println(collection);
        System.out.println("==================================");

        System.out.println("打印map："+map);//打印的顺序和你存放的顺序是不一样的

        String value = map.get("及时雨");
        String value2 = map.get("及时雨2");//获取不到返回为null
        String value3 = map.getOrDefault("及时雨2","高博");//获取不到返回默认值
        System.out.println(value);
        System.out.println(value2);
        System.out.println(value3);
        value = map.remove("悟净");//返回要删除的结点的 value值
        System.out.println(value);
        System.out.println(map.containsKey("及时雨"));
        System.out.println(map.containsValue("宋江"));

    }
}
